A CSP may be defined as a triplet P=<V, D, C>, involving a set of variables, V={v1, . . . , vn}, which take discrete values from their corresponding finite domains D={Dv1, . . . , Dvn}, and a set of constraints C={C1, . . . , Cm}. A constraint is an entity that restricts the values of one or more variables it relates to. For example, a constraint may be C1>C2+C3. As another example, a constraint may be (C1>C2) OR (C3<C4 AND C1=5). The constraint may utilize arithmetic operators, logic operators, or the like. In some exemplary embodiments, constraints may be presented as first order logic formulas over the variables.
A solution to the CSP problem is a single assignment of each variable such that the value of the variable belongs to its corresponding domain, and all the constraints are satisfied.
One of the known solving techniques for CSP is Maintain Arc Consistency (MAC), which is described in Dechter R., “Constraint Processing” (USA) 2003, which is hereby incorporated by reference. In the MAC paradigm, CSP is solved by repeatedly performing two steps: (1) propagation and (2) instantiation.
The propagation step comprises restricting the domain of the variables to valid alternatives based on the constraints. Given a single constraint (formula/relation) and a set of variables values, a propagator reduces the domain of the variables, removing values that cannot be combined with any set of values from the other variables to satisfy the constraint. If none of the values is legal, a backtracking step is invoked.
The instantiation step is performed after the propagation step completes all possible propagations in each constraint alone (Arc). A variable is chosen and instantiated to a single value or sub-domain out of the current domain.
The instantiation has an impact on solver efficiency and the time it takes for the solution to be determined. Heuristics may be applied to reduce the number of backtracks and to gain performance speed-up. Many different types of heuristics are known in the literature, such as selecting the variables based on an order defined based on a constraint network, based on variables' domains, or based on a manual definition by a user.
CSP solver may be utilized in variety fields, such as for example verification, automatic scheduling, resource allocation algorithms, or the like. Generally, CSP solver solves an NP problem, or under some constraints an NP-complete problem.